/*
 * findNumInArray.cpp
 *
 *  Created on: Sep 9, 2012
 *      Author: jeffrey
 */
#include<iostream>
#include<vector>
using namespace std;
class FindNumInArray{
public:
	static vector<int> findNum(int array[], int n, int num){
		int s=0,e=n-1;
		int mid=(s+e)/2;
		while(s<=e){
			if(array[mid]==num)
				break;
			else if(array[mid]>num)
				e=mid-1;
			else
				s=mid+1;
			mid=(s+e)/2;
		}
		if(s>e)
			return vector<int>();
		int start=findLeft(array,0,mid,num);
		int end=findRight(array,mid,n-1,num);
		vector<int> result;
		result.push_back(start);
		result.push_back(end);
		return result;
	}
private:
	// find largest number that is less than num
	static int findLeft(int array[], int s, int e, int num){
		while(s<e){
			int mid=(s+e+1)/2;
			if(array[mid]>=num)
				e=mid-1;
			else
				s=mid;
		}
		return array[s]<num?s:s-1;
	}
	// find smallest number that is greater than num
	static int findRight(int array[], int s, int e, int num){
		while(s<e){
			int mid=(s+e)/2;
			if(array[mid]<=num)
				s=mid+1;
			else
				e=mid;
		}
		return array[e]>num?e:e+1;
	}
};

//int main(){
//	int array[] = { 0,1,2,3,3,3,4,4,5,5,5,6,6,6,10,10,10};
//	vector<int> result=FindNumInArray::findNum(array,sizeof(array)/sizeof(int),0);
//	if(result.empty())
//		cout<<"Can not find the number"<<endl;
//	else
//		cout<<"[ "<<result[0]<<","<<result[1]<<"]"<<endl;
//}

